class Solution {
public:
	TreeNode* find_r_last(TreeNode* root){ //找到root的最右有效节点
		if(!root){
            return nullptr;
        }
        if(root->right){
			return find_r_last(root->right);
		}
		
		return root;
	} 

	void dfs(TreeNode* root){
		if(!root){
			return;
		}
		
        dfs(root->left); //先把所有左子树解决
        if(root->left){ //如果左子树存在
            TreeNode* r_last=find_r_last(root->left); //先找到左子树最右有效节点
            TreeNode* zs=root->right;

            root->right=root->left; //将解决好的左子树直接变成右子树
            root->left=nullptr; //将左子树置空
            r_last->right=zs; //将未处理的右子树直接接到解决好的左子树最右有效节点 右子节点上
        }
        dfs(root->right); //解决右子树
	}

    void flatten(TreeNode* root) {
        dfs(root);
    }
};